import java.util.*;

public class Solution37 {

    int[] dx={0,0,0,1,1,1,2,2,2};
    int[] dy={0,1,2,0,1,2,0,1,2};
    boolean flag=false;

    public void solveSudoku(char[][] board) {
        Queue<int[]> queue=new LinkedList<>();
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                if (board[i][j]=='.'){
                    int conf=confirm(i,j,board);
                    if (conf!=-1){
                        queue.offer(new int[]{i,j,conf});
                    }
                }
            }
        }
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            board[t[0]][t[1]]=(char)(t[2]+'0');
            int x=deal(t[0]),y=deal(t[1]);
            for (int i=0;i<9;i++){
                if (board[i][t[1]]=='.') {
                    int conf = confirm(i, t[1], board);
                    if (conf != -1) {
                        queue.offer(new int[]{i, t[1], conf});
                    }
                }
                if (board[t[0]][i]=='.') {
                    int conf = confirm(t[0], i, board);
                    if (conf != -1) {
                        queue.offer(new int[]{t[0], i, conf});
                    }
                }
                if (board[x+dx[i]][y+dy[i]]=='.'){
                    int conf = confirm(x+dx[i], y+dy[i], board);
                    if (conf != -1) {
                        queue.offer(new int[]{x+dx[i], y+dy[i], conf});
                    }
                }
            }
        }
        List<int[]> list=new ArrayList<>();
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                if (board[i][j]=='.'){
                    list.add(new int[]{i,j});
                }
            }
        }
        dfs(0,list,board);
    }

    private void dfs(int k, List<int[]> list, char[][] board) {
        if (k==list.size()){
            flag=true;
            return;
        }
        List<Integer> l=getList(board,list.get(k)[0],list.get(k)[1]);
        for (Integer integer : l) {
            board[list.get(k)[0]][list.get(k)[1]]=(char)(integer+'0');
            dfs(k+1,list,board);
            if (flag){
                return;
            }
            board[list.get(k)[0]][list.get(k)[1]]='.';
        }
    }

    private List<Integer> getList(char[][] board, int i, int j) {
        List<Integer> ans=new ArrayList<>();
        int[] f=new int[10];
        Arrays.fill(f,1);
        int x=deal(i),y=deal(j);
        for (int k=0;k<9;k++){
            if (board[i][k]!='.') {
                f[board[i][k] - '0'] = 0;
            }
            if (board[k][j]!='.') {
                f[board[k][j] - '0'] = 0;
            }
            if (board[x+dx[k]][y+dy[k]]!='.') {
                f[board[x + dx[k]][y + dy[k]] - '0'] = 0;
            }
        }
        for (int k=1;k<=9;k++){
            if (f[k]==1) {
                ans.add(k);
            }
        }
        return ans;
    }

    private int confirm(int i, int j, char[][] board) {
        int[] f=new int[10];
        Arrays.fill(f,1);
        int x=deal(i),y=deal(j);
        for (int k=0;k<9;k++){
            if (board[i][k]!='.') {
                f[board[i][k] - '0'] = 0;
            }
            if (board[k][j]!='.') {
                f[board[k][j] - '0'] = 0;
            }
            if (board[x+dx[k]][y+dy[k]]!='.') {
                f[board[x + dx[k]][y + dy[k]] - '0'] = 0;
            }
        }
        int count=0;
        int ans=0;
        for (int k=1;k<=9;k++){
            if (f[k]==1) {
                count++;
                ans = k;
            }
        }
        return count==1?ans:-1;
    }

    private int deal(int i) {
        return i-i%3;
    }

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'.', '.', '9', '7', '4', '8', '.', '.', '.'},
                {'7', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '2', '.', '1', '.', '9', '.', '.', '.'},
                {'.', '.', '7', '.', '.', '.', '2', '4', '.'},
                {'.', '6', '4', '.', '1', '.', '5', '9', '.'},
                {'.', '9', '8', '.', '.', '.', '3', '.', '.'},
                {'.', '.', '.', '8', '.', '3', '.', '2', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '6'},
                {'.', '.', '.', '2', '7', '5', '9', '.', '.'}};
        new Solution37().solveSudoku(board);
        for (char[] chars : board) {
            System.out.println(chars);
        }
    }
}
